package leecode;

import java.util.Arrays;

/**
 * @Classname
 * @Description TODO
 * @Date 2021/7/19 19:27
 * @Created by Alberthch
 * 题目：最高频元素的频数
 */
class Solution_1838 {
    public static int maxFrequency(int[] nums, int k) {
        // 调包进行排序
        Arrays.sort(nums);
        int n = nums.length;

        // total表示将[l,r]区间元素全部变成莫为元素的操作次数
        long total = 0;

        // l,r表示左右边界
        int l = 0;

        // res维护满足限制的最大区间元素数量
        int res = 1;

        // 每次r的递增，就是滑动窗口右移
        for (int r = 1; r < n; r++) {

            // nums[r]为目标元素，(nums[r] - nums[r - 1]) * (r - l)表示要把num[l]到num[r]的所有元素都变成num[r]的操作次数
            total += (long) (nums[r] - nums[r - 1]) * (r - l);

            // 操作次数大于所给的k，则收缩边界，左边界右移
            while (total > k) {

                // 左移一次，其操作次数会减少nums[r] - nums[l]
                total -= nums[r] - nums[l];
                ++l;
            }

            // 区间内元素数量就是频数，可能会有很多个可行解，但是只保留最优解
            res = Math.max(res, r - l + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,2,4};
        System.out.println(maxFrequency(nums,2));
    }
}


